package java;

public class Question10 {
    public static void main(String[] args) {
        String str1 = "aa";
        String str2 = ".*aa";
        System.out.println(myIsMatch(str1,str2));
        System.out.println(isMatch(str1,str2));
    }

    public static boolean isMatch(String text, String pattern) {
        if (pattern.isEmpty()) {
            return text.isEmpty();
        }
        boolean first_match = (!text.isEmpty()
                && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

        if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
            return (isMatch(text, pattern.substring(2)) ||
                    (first_match && isMatch(text.substring(1), pattern)));
        } else {
            return first_match && isMatch(text.substring(1), pattern.substring(1));
        }
    }

    /**
     * 核心：递归思想可以处理分支问题，循环不可以。
     * @param s
     * @param p
     * @return
     */
    public static boolean myIsMatch(String s, String p) {
        if (p.isEmpty()){
            return s.isEmpty();
        }
        boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
        if (firstMatch){
            if (p.length() >= 2 && p.charAt(1) == '*'){
                return myIsMatch(s,p.substring(2)) || myIsMatch(s.substring(1),p);
            }else {
                return myIsMatch(s.substring(1),p.substring(1));
            }
        }else {
            if (p.length() >= 2 && p.charAt(1) == '*'){
                return myIsMatch(s,p.substring(2));
            }else {
                return false;
            }
        }
    }

}
